'''
贪心算法
    贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解

    贪心算法并不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解.要会判断一个问题能否用贪心算法来计算

'''
'''
找零问题
    假设商店老板需要找零n元钱,钱币的面额有:100,50,20,5,1,如何找零使得所需钱币的数量最少
    
'''
t = [100,50,20,5,1]
def change(t,n):
    m = [0 for _ in range(len(t))]
    for i,money in enumerate(t): # 使用enumerate遍历面值列表t，i是索引，money是当前面值
        m[i] = n // money # 计算当前面值最多能使用的数量：总金额n除以当前面值的整数部分
        n = n % money # 更新剩余需要找零的金额：取n除以当前面值的余数
    return m,n

print(change(t,376))